package com.cskaoyan.www.linked;

import java.util.Objects;

/**
 *  准备自己手动实现一个数据容器(手动实现一个集合类)
 *
 *  1, 数据容器/集合类:  使用者者角度,关注的是普通的根据内容的增删改查的api
 *  2, 希望逻辑结构上:  希望这个容器在组织(存储)数据的时候,
 *                      组织方式表现的数据结构, 线性表
 *     因为线性表是一个有序序列, 所以线性表最重要的表现, 元素是有位序的(下标)
 *     这也就意味着着
 *     如果我们希望MyLinkedList从逻辑结构表现为线性表, 就要体现下标问题
 *     怎么体现下标问题?  提供可以根据下标的增删改查
 *  3, 物理结构:  MyLinkedList底层真正存储数据的物理结构: 数组 or 链表
 *                使用链表:  使用单向链表
 *
 */
public class MyLinkedList {

    private Node head; // MyLinkedList底层的物理结构的单链表的头结点
    private int size; //  用来记录链表中存储了多少数据

    // -------一个普通容器应该具有的根据内容的增删改查方法
    // add
    // remove
    // contains
    // set
    //  ------希望MyLinkedList它逻辑结构表现为线性表:
    // -------提供根据下标操作的: 增删改查
    // add
    // remove
    // get
    // set

    /**
     * MyLinkedList 作为数据容器/集合类存在的根据内容的添加方法
     * @param value: 要添加的内容
     * @return: 添加是否成功
     */
    public boolean add(String value){
        // 第一次添加
        if (isEmpty()){
            // 链表为空
            head = new Node(value);
            size++;
            return true;
        }
        // 走到这, 链表不空:  因为没有指明位置, 默认添加到尾部
        //  TODO: 1, 先找到当前的尾结点,  找到尾结点之后, 把新的value构建结点添加到尾部

        Node mid = head; // 定义一个从头向后遍历的结点

        // 遍历结点下一个结点存在 : 说明不是尾结点, 向后遍历
        while (mid.next != null){
            mid = mid.next;
        }

        // mid就是当前链表的尾结点
        mid.next = new Node(value);
        size++;
        return true;
    }
    /**
     * MyLinkedList作为数据容器的根据内容的删除方法
     * @param value: 要删除的内容
     * @return: 删除是否成功
     */
    public boolean remove(String value){
        // 链表为空
        if (isEmpty()){
            // return false;
            throw new RuntimeException("list is empty");
        }
        // 链表不空, 可以删除
        // TODO: 先找到要删除的结点, 再删除
        //  删除: 1, 删除的是头结点 2, 删除的是中间或者尾结点

        // 1, 先判断是否为头结点
        // 让头结点存储的内容和要删除的内容进行比较
        // if (head.value.equals(value)    ){
        if (Objects.equals(head.value, value)){
            // 删除是头结点
            head = head.next;
            size--;
            return true;
        }

        // 意味着删除的是: 中间或者尾结点, 先找
        Node mid = head;

        // 判断: 遍历结点的下一个结点存在, 并且, 下一个结点也不是要查找删除的值
        //       ----> 向后继续遍历
        while (mid.next != null  && !Objects.equals(mid.next.value, value) ){
            mid = mid.next;
        }

        // 走到这:
        // 1, mid.next == null, 意味着这个链表中, 根本没有存储这个要删除的内容
        // 2, 找到了,  而且mid还是要删除结点的前一个

        // 没找到
        if (mid.next == null){
            return false;
        }

        // 找到了
        mid.next = mid.next.next;
        size--;

        return true;
    }
    /**
     * MyLinkedList作为数据容器的根据内容的查找方法
     * @param value: 要查找的内容
     * @return: 是否存在
     */
    public boolean contains(String value){
        // 判断链表是否为空
        if (isEmpty()){
            // return false;
            throw new RuntimeException("list is empty");
        }

        Node mid = head; // 定义一个临时结点, 用来遍历链表

        // 意味着当前遍历结点存在, 并且当前遍历接电脑存储的内容也不是要找的内容
        //   ---> 向后遍历
        while (mid != null &&  !Objects.equals(mid.value, value)){
            mid = mid.next;
        }

        // 1. 遍历完整个链表没有找到
        if (mid == null){
            return false;
        }
        // 2, 找到了
        return true;
    }
    /**
     * MyLinkedList作为数据容器根据内容的修改方法
     * @param oldValue: 被替换的旧值
     * @param newValue: 用来替换的新值
     * @return: 替换是否成功
     */
    public boolean set(String oldValue, String newValue){
        // 判断链表是否为空
        if (isEmpty()){
            // return false;
            throw new RuntimeException("list is empty");
        }

        Node mid = head; // 定义一个临时结点, 用来遍历链表

        // 意味着当前遍历结点存在, 并且当前遍历接电脑存储的内容也不是要找的内容
        //   ---> 向后遍历
        while (mid != null &&  !Objects.equals(mid.value, oldValue)){
            mid = mid.next;
        }

        // 1. 遍历完整个链表没有找到
        if (mid == null){
            return false;
        }
        // 2, mid就是要替换的结点 , 替换
        mid.value = newValue;
        return true;
    }

    /**
     * MyLinkedList从逻辑上作为线性表的体现: 根据下标的添加方法
     * @param index: 要添加的下标位置
     * @param value: 添加的内容
     * @return: 添加是否成功
     */
    public boolean add(int index, String value){
        // 判断一下下标是否合法
        if (index < 0 || index > size){
            throw new IllegalArgumentException("paramer is Illegal");
        }


        // 1, 添加的是否是头位置
        if (index == 0){
            head = new Node(value, head);
            size++;
            return true;
        }

        // 2, 添加的是否是尾位置
        if (index == size){
            return add(value);
        }

        // 3, 添加中间某个位置
        //    先根据下标找到要添加位置的前一个位置

        Node mid = head;
        int tag = 1;

        while (tag != index){
            mid = mid.next;
            tag++;
        }
        // 上述循环结束, mid就是要添加位置的前一个位置结点

        mid.next = new Node(value, mid.next);
        size++;

        return true;
    }
    /**
     * MyLinkedList从逻辑上作为线性表的体现: 根据下标的删除方法
     * @param index: 要删除的线性表表现的下标位置
     * @return: 被删除的数据
     */
    public String remove(int index){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal ");
        }

        // 1, 删除的是否是头位置
        if (index == 0){
            // 保存删除的值
            String oldValue = head.value;
            head = head.next;
            size--;
            return oldValue;
        }

        // 2, 删除中间和尾的位置: 先找到再删除
        Node mid = head;
        int tag = 1;

        while (tag != index){
            mid = mid.next;
            tag++;
        }

        // mid是要删除位置的前一个位置
        String oldValue = mid.next.value;

        // 删除
        mid.next = mid.next.next;
        size--;

        return oldValue;
    }

    /**
     * MyLinkedList从逻辑上作为线性表的体现: 根据下标的查找方法
     * @param index: 要查找的下标位置
     * @return: 这个位置存储的内容
     */
    public String  get(int index){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal ");
        }


        // 根据下标查找
        Node mid = head;
        int tag = 0;

        while (tag != index){
            mid = mid.next;
            tag++;
        }

        // mid就是要查找的位置

        return mid.value;
    }
    /**
     * MyLinkedList从逻辑上作为线性表的体现: 根据下标的修改方法
     * @param index: 要修改的下标位置
     * @param newValue: 用来覆盖的新值
     * @return: 被覆盖的旧值
     */
    public String  set(int index, String newValue){
        // 判断下标是否合法
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("paramer is Illegal ");
        }


        // 根据下标查找
        Node mid = head;
        int tag = 0;

        while (tag != index){
            mid = mid.next;
            tag++;
        }

        // mid就是要查找的位置 --> 替换
        String oldValue = mid.value;
        mid.value = newValue;

        return oldValue;
    }


    public boolean isEmpty(){
        return size == 0;
    }

    // 单链表的结点
    class Node{
        String value; // 值域
        Node next; // 指针域

        public Node(String value) {
            this.value = value;
        }

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
